//
// Description: STL之partial_sort()与partial_sort_copy()使用
//              适用于仅需要按照一定排序算法进行排序的部分元素，例如在100个元素中找出最小的10个
// Created by Loading on 2021/5/28.
//

/*
 * 容器支持的迭代器类型必须为随机访问迭代器。这意味着，partial_sort() 函数只适用于 array、vector、deque 这 3 个容器。
 * 当选用默认的升序排序规则时，容器中存储的元素类型必须支持 < 小于运算符；同样，如果选用标准库提供的其它排序规则，元素类型也必须支持该规则底层实现所用的比较运算符；
 * partial_sort() 函数在实现过程中，需要交换某些元素的存储位置。因此，如果容器中存储的是自定义的类对象，则该类的内部必须提供移动构造函数和移动赋值运算符。
 */

#include <bits/stdc++.h>

using namespace std;

//自定义排序规则
bool myCmp(int i, int j) {
    return i > j;
}

int main() {
    vector<int> vec = {3, 2, 5, 4, 1, 6, 9, 7};

    /* partial_sort() */
    /* 平均时间复杂度 NlogM，N为vec长度，M为需排序的长度 */
    //默认升序的排序规则
    partial_sort(vec.begin(), vec.begin() + 4, vec.end());
    cout << "默认升序排序前4个:" << endl;
    for (auto &x : vec) {
        cout << x << " ";
    }
    cout << endl;

    //自定义排序规则
    partial_sort(vec.begin(), vec.begin() + 4, vec.end(), myCmp);
    cout << "自定义排序前4个:" << endl;
    for (auto &x : vec) {
        cout << x << " ";
    }
    cout << endl;

    /* partial_sort_copy() */
    /* 不改变原来容器元素，将选定的元素拷贝到另外的数组或容器中，再对这部分元素排序 */
    /* 平均时间复杂度 Nlog(min(M, N))，N为vec长度，M为需排序的长度 */
    list<int> l = {3, 2, 5, 4, 1, 6, 9, 7};
    vector<int> vec2(5);
    //copy默认升序的排序规则
    partial_sort_copy(l.begin(), l.end(), vec2.begin(), vec2.end());
    cout << "copy默认升序排序前5个:" << endl;
    for (auto &x : vec2) {
        cout << x << " ";
    }
    cout << endl;

    //copy自定义排序规则
    partial_sort_copy(l.begin(), l.end(), vec2.begin(), vec2.end(), myCmp);
    cout << "copy自定义排序前5个:" << endl;
    for (auto &x : vec2) {
        cout << x << " ";
    }
    cout << endl;
}